package 滑动窗口And双指针.双指针;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/12 21:30
 */
public class leetcode6355统计公平数对的数目 {

    /*
  贴 一个 arignote 的代码
  真的 看不懂! 是怎么 做到的!
 时间复杂度 还是 N * LogN
 */
    class Solution {

        public long countFairPairs(int[] nums, int lower, int upper) {
            Arrays.sort(nums);
            long count = 0;
            for (int i = 0, j = nums.length - 1, k = nums.length - 1; i < nums.length; i++) {
                for (; j >= 0 && nums[i] + nums[j] >= lower; j--) {
                }
                for (; k >= 0 && nums[i] + nums[k] > upper; k--) {
                }
                count += k - j - (i > j && i <= k ? 1 : 0);
            }
            return count / 2;
        }
    }

    /*
     先解决 一个 引申的 问题:
     给出 数组 nums[], 求 0  <= i < j < n ,的范围 内 nums[i] + nums [j] <= upper 的 数对, 个数?
     一:
      排序 + 滑动窗口And双指针.双指针 :
      注意一下 这个思想!

      二:
      排序 + 二分: (跟下面的解法 是 一致的 ,还是要 理解枚举的范围) 代码同下面的解法

     */



    /*
     比较容易理解, 并且 快!
     求    l <= x <= r 范围内的个数
     转换为   [0 , r] 内的 个数   减去    [0, l) 的个数  ( 注意 区间的开闭)
     */
    public int solutionDoublePointer(int nums[],int upper){
        int l = 0,r = nums.length - 1;
        /*
         r 向  左移动  nums[i] + nums[j] 会变小
         l 向右移动 nums[i] + nums[j] 的值 会变大
         */
        int ans = 0;
        while(l < r){ // 只有 一个元素, 没办法组成数对
            if(nums[l] + nums[r] <= upper){// 说明 l 和 [l + 1, r] 内任意 一个点 都能组成 满足要求的数对, 所以 [l , r] 满足的 要求的数对 r - l (两个 一对)
                ans +=  r - l;
                l++; // l 向右移动
            }
            else{
                r--;
            }
        }
        return ans;
    }

    public long solution(int nums[],int lower,int upper){
        long ans = 0;
        Arrays.sort(nums);
        int countLower = solutionDoublePointer(nums,lower - 1);
        int countUpper = solutionDoublePointer(nums,upper);
        ans = countUpper - countLower;
        return ans;
    }



}
